package chapter03_binaryTree;

/**
 * 描述：
 *      判断t1中是否有与t2完全相同的拓扑结构
 * @author hl
 * @date 2021/5/28 10:50
 */
public class IsSubTree {

    /**
     * 先以先序遍历序列化两个二叉树t1Str和t2Str，然后用KMP算法判断t1Str是否包含t2Str这个子串
     * @param t1
     * @param t2
     * @return
     */
    public boolean isSubTree(Node t1, Node t2){
        String t1Str = serialByPre(t1);
        String t2Str = serialByPre(t2);
        return kmp(t1Str, t2Str);
    }

    private boolean kmp(String str1, String str2) {
        //1.求出Next数组
        int n1 = str1.length(), n2 = str2.length();
        int[] next = getNextArray(str2);
        int i = 0, j = 0;
        while(i < n1 && j < n2){
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
                j++;
            }else if (next[j] == -1) {
                i++;
            }else{
                j = next[j];
            }
        }
        return j == n2;
    }

    private int[] getNextArray(String str) {
        int n = str.length();
        if (n == 1) {
            return new int[]{-1};
        }
        //next[i]表示str在从0~i-1的字符串前后缀相同的字符数量
        int[] next = new int[n + 1];
        next[0] = -1;
        next[1] = 0;
        int pos = 2, cn = 0;
        while(pos <= n){
            if (str.charAt(pos - 1) == str.charAt(cn)) {
                next[pos] = ++cn;
            }else if (cn > 0) {
                cn = next[cn];
            }else{
                next[pos] = 0;
            }
        }
        return next;
    }

    public String serialByPre(Node head){
        if (head == null) {
            return "#!";
        }
        String str = head.val +"!";
        str += serialByPre(head.left);
        str += serialByPre(head.right);
        return str;
    }


    /**
     * 时间复杂度O(N * M)
     * @param t1
     * @param t2
     * @return
     */
    public boolean isSubTree2(Node t1, Node t2){
        if (t1 == null) {
            return false;
        }
        return check(t1, t2) || isSubTree2(t1.left, t2) || isSubTree2(t1.right, t2);
    }

    private boolean check(Node t1, Node t2) {
        if (t1 != t2) {
            return false;
        }
        return t2 == null || (check(t1.left, t2.left) && check(t1.right, t2.right));
    }

}
